package com.lisp.algorithm.book.c13;

import java.util.LinkedList;
import java.util.List;

import com.lisp.algorithm.util.Assert;

public class AvlTree {

	public static void main(String[] args) {
		/*
		for(int i=1; i<10; i++) {
			insert(i);
		}
		bfs(false, true);
		
		for(int i=10; i>=0; i--) {
			delete(i);
			bfs(true, true);
		}
		*/

		for(int i=0; i<1000000; i++) {
			for(int j=0; j<10; j++) {
				int x = new java.util.Random().nextInt(100);
				insert(x);
				bfs(false, true);
			}
			
			// System.out.println("start delete test.....");
			
			for(int j=0; j<100; j++) {
				int x = new java.util.Random().nextInt(100);
				bfs(false, true);
				// System.out.println("----------delete " + x);
				delete(x);
			}
			root = null;
			System.out.println(i);
		}
	}
	
	static Node root;
	
	static Node NULL = new Node(-1, null, null, null, 0);
	
	public static void delete(int key) {
		Node node = search(key);
		delete(node);
	}
	
	public static void delete(Node n) {
		if(n == null || n == NULL) {
			return;
		}
		
		if(n.left == NULL) {
			transplant(n, n.right);
			fixDelete(n.right);
		} else if(n.right == NULL) {
			transplant(n, n.left);
			fixDelete(n.left);
		} else {
			Node successor = leftMost(n.right);
			if(successor.parent == n) {
				transplant(n, successor);
				successor.left = n.left;
				n.left.parent = successor;
				
				successor.height = n.height;
				
				if(successor.right == NULL) {
					successor.right.parent = successor;
				}
				fixDelete(successor.right);
			} else {
				Node sRight = successor.right;
				transplant(successor, sRight);
				
				transplant(n, successor);
				successor.left = n.left;
				n.left.parent = successor;
				
				successor.right = n.right;
				n.right.parent = successor;
				
				successor.height = n.height;
				
				fixDelete(sRight);
			}
		}
	}
	
	private static void fixDelete(Node n) {
		Node z = n.parent;
		while(z != NULL) {
			int balanceValue = balanceValue(z);
			if(balanceValue == 2 || balanceValue == -2) {
				int originHeight = z.height;
				Node newZ = fixDeleteHelper(z);
				if(newZ.height < originHeight) {
					z = newZ.parent;
				} else {
					return;
				}
			} else {
				int newHeight = newHeight(z);
				if(z.height > newHeight) {
					z.height = newHeight;
					z = z.parent;
				} else {
					return;
				}
			}
		}
	}

	private static Node fixDeleteHelper(Node z) {
		int balanceValue = balanceValue(z);
		if(balanceValue > 0) {
			Node y = z.left;
			int ybv = balanceValue(y);
			if(ybv >= 0) {
				return fixInsert(y.left, y, z);
			} else {
				return fixInsert(y.right, y, z);
			}
		} else {
			Node y = z.right;
			int ybv = balanceValue(y);
			if(ybv <= 0) {
				return fixInsert(y.right, y, z);
			} else {
				return fixInsert(y.left, y, z);
			}
		}
	}

	public static void insert(int key) {
		if(root == null || root == NULL) {
			root = new Node(key, NULL, NULL, NULL, 1);
		} else {
			insert(key, root);
		}
	}
	
	private static void insert(int key, Node node) {
		if(key <= node.key) {
			Node left = node.left;
			if(left == NULL) {
				Node newNode = new Node(key, node, NULL, NULL, 1);
				node.left = newNode;
				fixInsert(newNode);
			} else {
				insert(key, left);
			}
		} else {
			Node right = node.right;
			if(right == NULL) {
				Node newNode = new Node(key, node, NULL, NULL, 1);
				node.right = newNode;
				fixInsert(newNode);
			} else {
				insert(key, right);
			}
		}
	}
	
	private static void fixInsert(Node newNode) {
		Node x = null, y = newNode;
		Node z = newNode.parent;
		while(z != NULL) {
			int originHeight = originHeight(z);
			int newHeight = newHeight(z);
			if(newHeight > originHeight) {
				int balanceValue = balanceValue(z);
				if(balanceValue == 2 || balanceValue == -2) {
					fixInsert(x, y, z);
					return;
				} else {
					z.height = newHeight;
					x = y;
					y = z;
					z = z.parent;
				}
			} else {
				return;
			}
		}
	}
	
	private static Node fixInsert(Node x, Node y, Node z) {
		if(z.left == y) {
			if(y.left == x) {
				rightRotate(z, y);
				z.height = newHeight(z);
				y.height = newHeight(y);
				return y;
			} else {
				leftRotate(y, x);
				rightRotate(z, x);
				y.height = newHeight(y);
				z.height = newHeight(z);
				x.height = newHeight(x);
				return x;
			}
		} else {
			if(y.right == x) {
				leftRotate(z, y);
				z.height = newHeight(z);
				y.height = newHeight(y);
				return y;
			} else {
				rightRotate(y, x);
				leftRotate(z, x);
				z.height = newHeight(z);
				y.height = newHeight(y);
				x.height = newHeight(x);
				return x;
			}
		}
	}
	
	// origin != null && n != null
	private static void transplant(Node origin, Node n) {
		n.parent = origin.parent;
		if(origin.parent == NULL) {
			root = n;
		} else {
			if(origin.parent.left == origin) {
				origin.parent.left = n;
			} else {
				origin.parent.right = n;
			}
		}
	}
	
	private static void leftRotate(Node parent, Node right) {
		Node middleLeaf = right.left;
		transplant(parent, right);
		
		right.left = parent;
		parent.parent = right;
		
		parent.right = middleLeaf;
		if(middleLeaf != NULL) {
			middleLeaf.parent = parent;
		}
	}
	
	private static void rightRotate(Node parent, Node left) {
		Node middleLeaf = left.right;
		transplant(parent, left);
		
		left.right = parent;
		parent.parent = left;
		
		parent.left = middleLeaf;
		if(middleLeaf != NULL) {			
			middleLeaf.parent = parent;
		}
	}

	private static int originHeight(Node n) {
		if(n == NULL) {
			return 0;
		} else {
			return n.height;
		}
	}
	
	private static int newHeight(Node n) {
		return Math.max(originHeight(n.left), originHeight(n.right)) + 1;
	}
	
	private static int balanceValue(Node n) {
		if(n == NULL) {
			return 0;
		} else {
			return originHeight(n.left) - originHeight(n.right);
		}
	}
	
	private static Node leftMost(Node n) {
		Node ret = n;
		while(ret.left != NULL) {
			ret = ret.left;
		}
		return ret;
	}

	public static void inorderTraverse(Node n) {
		if(n == NULL) {
			return;
		}
		inorderTraverse(n.left);
		System.out.print(n.key + "  ");
		inorderTraverse(n.right);
	}
	
	public static Node search(int key) {
		Node ret = root;
		while(ret != NULL && ret != null) {
			if(ret.key == key) {
				return ret;
			} else if(ret.key < key) {
				ret = ret.right;
			} else {
				ret = ret.left;
			}
		}
		return null;
	}
	
	public static void bfs(boolean print, boolean check) {
		if(print) {
			System.out.println("------------print tree start----------");
		}
		
		if(root == NULL) {
			System.out.println("empty tree");
			return;
		}
		
		List<NodeWrapper> q = new LinkedList<>();
		q.add(new NodeWrapper(root, 0));
		
		int currentLevel = 0;
		while(!q.isEmpty()) {
			NodeWrapper nw = q.remove(0);
			if(nw.node.left != NULL) {
				q.add(new NodeWrapper(nw.node.left, nw.level+1));
			}
			
			if(nw.node.right != NULL) {
				q.add(new NodeWrapper(nw.node.right, nw.level+1));
			}
			
			if(print) {
				if(currentLevel != nw.level) {
					currentLevel = nw.level;
					System.out.println();
				}
				
				System.out.println(nw.node);
			}
			
			if(check) {
				Node n = nw.node;
				Assert.isTrue(n.left == NULL || n.left.parent == n);
				Assert.isTrue(n.right == NULL || n.right.parent == n);
				Assert.isTrue(n.left == NULL || n.key >= n.left.key);
				Assert.isTrue(n.right == NULL || n.key <= n.right.key);
				Assert.isTrue(n.height == newHeight(n), n.toString() + "; newHeight=" + newHeight(n));
			}
		}
		
		if(print) {
			System.out.println("------------print tree end-------------");
		}
	}

	static class Node {
		private int key;
		private Node parent;
		private Node left;
		private Node right;
		private int height;
		
		public Node(int key, Node parent, Node left, Node right, int height) {
			this.key = key;
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.height = height;
		}
		
		public String toString() {
			return String.format("key=%s, height=%s, parentKey=%s", 
					key, height, parent == NULL ? -1 : parent.key);
		}
	}

	static class NodeWrapper {
		Node node;
		int level;
		
		public NodeWrapper(Node n, int level) {
			super();
			this.node = n;
			this.level = level;
		}
	}
}
